package org.myy.learn.hot.finish.双指针;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        for (int i=0; i<n; i++){
            if(nums[i] > 0){break;}
            if(i>0 && nums[i] == nums[i-1]){continue;} //ToDo 数组下标<0的情况
            int l = i+1, r = n-1;
            int target = -nums[i];
            while (l<r){
                int sum = nums[l]+nums[r];
                if(sum == target){
                    result.add(Arrays.asList(nums[l], nums[r], nums[i]));
                    l++;
                    r--;
                    while (l<r && nums[l] == nums[l-1]){l++;}//ToDo
                    while (l<r && nums[r] == nums[r+1]){r--;}
                }else if(sum > target){
                    r--;
                }else {
                    l++;
                }
            }
        }
        return result;
    }

}
